#include <cstdlib>
#include <ctime> 
#include "RankSet.h"
#include "Vertex.h"
#include "Helpers.h"

//---------------------------------------------------------------------------------
// Public
//---------------------------------------------------------------------------------

//---------------------------------------------------------------------------------
// Ctor
// Initializes random and sets index to 0
//---------------------------------------------------------------------------------
RankSet::RankSet(Graph *graph, int rank)
{
	srand((unsigned)time(0));
	m_MaxIndex = 0;
	m_Rank = rank;
	m_Graph = graph;
}

//--------------------------------------------------------------------------------
// GetRandomVertex
// Returns: a random vertex from the set or NULL if none
// removes it from container
//---------------------------------------------------------------------------------
Vertex* RankSet::GetRandomVertex() 
{
	if (m_MaxIndex == 0)
	{
		return NULL;
	}

	// Get a random index between 0 and max index (inclusive)
	long randomIndex = rand() % (m_MaxIndex+1); 

	// Returns iterator to 1st item that is >= randomIndex
	RankSetIterator it = m_VertexSet.lower_bound(randomIndex); 
	// If none is found, end is returned
	if (it == m_VertexSet.end())
	{
		it--;
	}

	Vertex* vertex = it->second;
		
	return vertex;
}

//--------------------------------------------------------------------------------
// InsertNewVertex: Adds vertex to RankSet and updates its container
// Parameters:
// Vertex* vertex - vertex to insert
//--------------------------------------------------------------------------------
void RankSet::InsertNewVertex(VertexBase* vertex)
{
	Vertex* currentVertex = dynamic_cast<Vertex*>(vertex);
	InsertVertex(currentVertex, true);
}

//--------------------------------------------------------------------------------
// RemoveVertex: Removes vertex from RankSet
// Parameters:
// Vertex* vertex - vertex to remove
//--------------------------------------------------------------------------------
void RankSet::RemoveVertex(Vertex* vertex)
{
	RankSetIterator it = Find(vertex);
	if (it == m_VertexSet.end())
	{
		throw new GraphColoringException("Erasing vertex "+vertex->PrintName()+" from RankSet it doesn't belong to");
	}
	
	int removedIndex = it->first;
	m_VertexSet.erase(it);
	UpdateMaxIndexIfNeeded(removedIndex);

	// Vertex is not in this set anymore - clear pointer
	vertex->ResetContainer();

}

//--------------------------------------------------------------------------------
// Count
// Returns: Number of vertices in RankSet
//--------------------------------------------------------------------------------
const long RankSet::Count() 
{
	return m_VertexSet.size();
}

//--------------------------------------------------------------------------------
// IsEmpty
// Returns: True if RankSet has no vertices, false otherwise
//--------------------------------------------------------------------------------
const bool RankSet::IsEmpty() 
{
	return Count() == 0;
}

//--------------------------------------------------------------------------------
// GetRank
// Returns: The rank all vertices in the RankSet have
//--------------------------------------------------------------------------------
const long RankSet::GetRank() const
{
	return m_Rank;
}

//--------------------------------------------------------------------------------
// Clone
// Returns: Deep copy
//--------------------------------------------------------------------------------
RankSet *RankSet::Clone()  const 
{
	RankSet *set = CloneFromDirectory(m_Graph, NULL);
	return set;
}

//--------------------------------------------------------------------------------
// CloneFromDirectory
// Returns: Deep copy, vertices pointers are taken from the supplied directory
// if directory is NULL, uses current vertex pointers.
// This function assumes that the vertex info in directory is correct,
// meaning the rank is right and all the neighbours think the vertex is in graph!
//--------------------------------------------------------------------------------
RankSet *RankSet::CloneFromDirectory(Graph *graph, VertexDirectory* dir)  const 
{
	RankSet* set;
	try
	{
		set = new RankSet(graph,m_Rank);
	}
	catch(std::bad_alloc *e) //memory allocation failed
	{
		e = NULL;
		Logger::LogMessage("memory allocation failed in RankSet::CloneFromDirectory. Rank set wasn't created.");
		return NULL;
	}
	
	map<long, Vertex*>::const_iterator it;
	// Go over all the vertices in this rankset
	for (it=m_VertexSet.begin() ; it != m_VertexSet.end(); it++ )
	{
		Vertex *vertex;
		vertex = VertexDirectory::GetVertexFromDirectory(it->second->Name(), dir);
		
		// We do not preserve indexes, they are unimportant
		// no updates needed - we assume directory info was already copied
		set->InsertVertex(vertex, false);
	}
	return set;
}


//--------------------------------------------------------------------------------
// ContainsVertex: returns true if the vertex belongs to this rankset
//--------------------------------------------------------------------------------
bool RankSet::ContainsVertex(Vertex *vertex)
{
	return (Find(vertex) != m_VertexSet.end());
}

//--------------------------------------------------------------------------------
// GetContainingGraph: returns graph this rank set belongs to
//--------------------------------------------------------------------------------
Graph *RankSet::GetContainingGraph()
{
	return m_Graph;
}

//--------------------------------------------------------------------------------
// InsertAllVerticesToNewGraph: Inserts all vertices to the new graph
// they will be taken from graph's vertexdirectory
//--------------------------------------------------------------------------------
void RankSet::InsertAllVerticesToNewGraph(Graph *newGraph)
{
	RankSetIterator it;
	for (it = m_VertexSet.begin(); it != m_VertexSet.end(); it++)
	{
		newGraph->InsertVertex(it->second, false);
	}
}

//--------------------------------------------------------------------------------
// Operator==: RankSets are compared by rank
//--------------------------------------------------------------------------------
bool RankSet::operator==(const RankSet &other) const
{ 
	return other.GetRank() == m_Rank;
}

//--------------------------------------------------------------------------------
// Operator!=: RankSets are compared by rank
//--------------------------------------------------------------------------------
bool RankSet::operator!=(const RankSet &other) const
{
	return !((*this)==other);
}

//--------------------------------------------------------------------------------
// Operator<: RankSets are compared by rank
//--------------------------------------------------------------------------------
bool RankSet::operator<(const RankSet &other) const
{
	return other.GetRank() < m_Rank;
}

//--------------------------------------------------------------------------------
// Operator>: RankSets are compared by rank
//--------------------------------------------------------------------------------

bool RankSet::operator>(const RankSet &other) const
{
	return other.GetRank() > m_Rank;
}

//--------------------------------------------------------------------------------
// Operator<=: RankSets are compared by rank
//--------------------------------------------------------------------------------
bool RankSet::operator<=(const RankSet &other) const
{
	return ((*this) < other) || ((*this) == other);
}

//--------------------------------------------------------------------------------
// Operator>=: RankSets are compared by rank
//--------------------------------------------------------------------------------
bool RankSet::operator>=(const RankSet &other) const
{
	return ((*this) > other) || ((*this) == other);
}

//--------------------------------------------------------------------------------
//Private
//--------------------------------------------------------------------------------

//-----------------------------------------------------------------
// GetMaxIndex: Returns maximal index
//-----------------------------------------------------------------
int RankSet::GetMaxIndex()
{
	map<long, Vertex*>::const_iterator it;
	int maxIndex = 0;
	for (it=m_VertexSet.begin() ; it != m_VertexSet.end(); it++ )
	{
		if (it->first > maxIndex)
		{
			maxIndex = it->first;
		}
	}
	return maxIndex;
}


//-----------------------------------------------------------------
// UpdateMaxIndexIfNeeded: Updates the maximal index if it was 
// removed
//-----------------------------------------------------------------
void RankSet::UpdateMaxIndexIfNeeded(int removedIndex)
{
	if (removedIndex == m_MaxIndex)
	{
		m_MaxIndex = GetMaxIndex();
	}
}

//-----------------------------------------------------------------
// Find : returns an iterator to vertex or end
//-----------------------------------------------------------------
RankSetIterator RankSet::Find(Vertex *vertex)
{
	RankSetIterator it;
	for (it = m_VertexSet.begin(); it != m_VertexSet.end(); it++)
	{
		if (it->second->Name() == vertex->Name())
		{
			return it;
		}
	}

	return it;

}

//-----------------------------------------------------------------
// InsertVertex : inserts a vertex to this set
// updateNeighbours - if this flag is true, updates neighbours
//-----------------------------------------------------------------
void RankSet::InsertVertex(Vertex *vertex, bool updateNeighbours)
{
	if (vertex->Rank() != m_Rank)
	{
		throw new GraphColoringException("Trying to insert a vertex into the wrong rankset!");
	}
	m_MaxIndex++;
	m_VertexSet[m_MaxIndex] = vertex;
	
	// vertex belongs to this rankset, update neighbours according to flag
	vertex->MoveToContainer(this, true, updateNeighbours);
}


